/**
 * @program: LeetCode
 * @description: LeetCode :  剑指 Offer II 067. 最大的异或
 * @author: WXY
 * @create: 2023-01-08 14:27
 * @Version 1.0
 **/
public class offer_twentytwo3_findMaximumXOR {
    public static int findMaximumXOR1(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                max = Math.max(max, nums[i] ^ nums[j]);
            }
        }
        return max;
    }

    public int findMaximumXOR(int[] nums) {
        Trie node = new Trie();
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            node.insert(nums[i]);
            max = Math.max(max, nums[i] ^ node.search(nums[i]));
        }
        return max;
    }

    private class Trie {
        Trie[] child;

        public Trie() {
            child = new Trie[2];
        }

        public void insert(int n) {
            Trie node = this;
            for (int i = 31; i >= 0; i--) {
                int index = (n >> i) & 1;
                if (node.child[index] == null) {
                    node.child[index] = new Trie();
                }
                node = node.child[index];
            }
        }

        public int search(int n) {
            Trie cur = this;
            int ans = 0;
            for (int i = 31; i >= 0; i--) {
                int index = (n >> i) & 1;
                int wantToBit = index ^ 1;
                if (cur.child[wantToBit] != null) {
                    index = wantToBit;
                }
                ans += index << i;
                cur = cur.child[index];
            }
            return ans;
        }
    }


}
